package org.example;

import java.util.Random;

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if(left == right) return;
        //随机数选择基准值key
        int key = nums[new Random().nextInt(right - left + 1) + left];

        //三路划分
        int l = left - 1, r = right + 1, cur = left;
        while(cur < r){
            if(nums[cur] < key){
                Swap(nums, ++l, cur++);
            }else if(nums[cur] == key){
                cur++;
            }else{
                //nums[cur] > key
                Swap(nums, --r, cur);
            }
        }
        quickSort(nums, left, l);
        quickSort(nums, r, right);
    }

    private void Swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}